//给你一个下标从 0 开始且长度为 n 的整数数组 differences ，它表示一个长度为 n + 1 的 隐藏 数组 相邻 元素之间的 差值 。更正式的
//表述为：我们将隐藏数组记作 hidden ，那么 differences[i] = hidden[i + 1] - hidden[i] 。 
//
// 同时给你两个整数 lower 和 upper ，它们表示隐藏数组中所有数字的值都在 闭 区间 [lower, upper] 之间。 
//
// 
// 比方说，differences = [1, -3, 4] ，lower = 1 ，upper = 6 ，那么隐藏数组是一个长度为 4 且所有值都在 1 和
// 6 （包含两者）之间的数组。 
// 
//
// 
// [3, 4, 1, 5] 和 [4, 5, 2, 6] 都是符合要求的隐藏数组。 
// [5, 6, 3, 7] 不符合要求，因为它包含大于 6 的元素。 
// [1, 2, 3, 4] 不符合要求，因为相邻元素的差值不符合给定数据。 
// 
// 
//
//
// 请你返回 符合 要求的隐藏数组的数目。如果没有符合要求的隐藏数组，请返回 0 。 
//
// 
//
// 示例 1： 
//
// 输入：differences = [1,-3,4], lower = 1, upper = 6
//输出：2
//解释：符合要求的隐藏数组为：
//- [3, 4, 1, 5]
//- [4, 5, 2, 6]
//所以返回 2 。
// 
//
// 示例 2： 
//
// 输入：differences = [3,-4,5,1,-2], lower = -4, upper = 5
//输出：4
//解释：符合要求的隐藏数组为：
//- [-3, 0, -4, 1, 2, 0]
//- [-2, 1, -3, 2, 3, 1]
//- [-1, 2, -2, 3, 4, 2]
//- [0, 3, -1, 4, 5, 3]
//所以返回 4 。
// 
//
// 示例 3： 
//
// 输入：differences = [4,-7,2], lower = 3, upper = 6
//输出：0
//解释：没有符合要求的隐藏数组，所以返回 0 。
// 
//
// 
//
// 提示： 
//
// 
// n == differences.length 
// 1 <= n <= 10⁵ 
// -10⁵ <= differences[i] <= 10⁵ 
// -10⁵ <= lower <= upper <= 10⁵ 
// 
//
// Related Topics 数组 前缀和 👍 33 👎 0


package LeetCode.editor.cn;


import java.util.Map;

/**
 * @author ldltd
 * @date 2025-04-21 10:19:01
 * @description 2145.统计隐藏数组数目
 
 */
 
public class CountTheHiddenSequences {
    public static void main(String[] args) {
    //测试代码
    CountTheHiddenSequences fun = new CountTheHiddenSequences();
    Solution solution= fun.new Solution();
        System.out.println(solution.numberOfArrays(new int[]{1,-3,4}, 1, 6));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /*
        * 1 -3 4
        * a b c d
        * b=a+1  c=b-3 d=c+4
        * 则每个数都可以表示成a的表达式
        * b=a+1 c=a+1-3 d=a+1-3+4  类似于一个前缀和
        * 初始a=0，然后记录所有表达式中的最大值最小值，只要不超过lower upper，就是一个合法区间
        * 示例的前缀和依次是 1  -2  2
        * 最大是2 最小是-2， 合法区间是[1,6]
        *a 的最小可能值：a_min = lower - min（因为 a + min >= lower）。
         a 的最大可能值：a_max = upper - max（因为 a + max <= upper）
         * 合法的 a 的取值范围是 [a_min, a_max]，
         * 所以合法的 a 的个数是 a_max - a_min + 1（如果 a_max >= a_min，否则为 0）
        * */
    public int numberOfArrays(int[] differences, int lower, int upper) {
        long max=Integer.MIN_VALUE,min=Integer.MAX_VALUE;
        long pre=0;
        for (int i = 0; i < differences.length; i++) {
            pre+=differences[i];
            max= Math.max(max,pre);
            min=Math.min(min,pre);
        }
        //开始比较区间
        // a must satisfy:
        // 1. a >= lower
        // 2. a <= upper
        // 3. a + min >= lower => a >= lower - min
        // 4. a + max <= upper => a <= upper - max
        long a_min = Math.max(lower, lower - min);
        long a_max = Math.min(upper, upper - max);

        if (a_max < a_min) {
            return 0;
        }
        return (int) (a_max - a_min + 1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
